package Hot100;

/**
 * @author zhangmin
 * @create 2021-12-23 11:05
 */
public class maxSubArray53 {
    /**53. 最大子数组和
     * 给你一个整数数组 nums ，请你找出一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。子数组 是数组中的一个连续部分。
     * dp[i]表示以i为结尾的最大子数组和的值，
     * dp[i]=Math.max(dp[i-1]+nums[i],nums[i])
     * */
    public int maxSubArray(int[] nums) {
        int n=nums.length;
        if (n==1) return nums[0];
        int dp_pre=nums[0],dp=dp_pre;
        int res=dp_pre;
        for (int i = 1; i < n; i++) {
            dp=Math.max(dp_pre+nums[i],nums[i]);
            dp_pre=dp;
            res=Math.max(res,dp);
        }
        return res;
    }
}
